package org.example.myleet.p783;

import org.example.myleet.Utils.TreeNode;

/**
 * 0 ms
 * Morris中序遍历，复杂度O(n)，空间复杂度O(1)
 * 总体思路是在最右叶子节点增加对cur节点的链接，将二叉树拉直变成链表访问
 */
public class Solution1 {
    public int minDiffInBST(TreeNode root) {
        int lastElement = -100000;
        int minDiff = Integer.MAX_VALUE;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                //当前节点有左子节点，寻找当前节点的前驱节点
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                //找到前驱节点，分两种情况讨论
                if (pre.right == null) {
                    //前驱节点未被访问过，则前驱节点连接到cur
                    pre.right = cur;
                    //然后进入左子节点深入
                    cur = cur.left;
                } else {
                    //前驱节点已经被访问过，其右子树被连接到cur，则断开连接，并访问当前节点，然后访问右子节点
                    pre.right = null;
                    minDiff = Math.min(minDiff, cur.val - lastElement);
                    lastElement = cur.val;
                    cur = cur.right;
                }
            } else {
                //当前节点没有左子节点，则访问当前节点，然后访问右子节点
                minDiff = Math.min(minDiff, cur.val - lastElement);
                lastElement = cur.val;
                cur = cur.right;
            }
        }
        return minDiff;
    }
}
